package com.cb2.algorithm.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <a href="https://leetcode.cn/problems/merge-k-sorted-lists/">合并 K 个升序链表(Merge k Sorted Lists)</a>
 * <p>给你一个链表数组，每个链表都已经按升序排列。</p>
 * <p>请你将所有链表合并到一个升序链表中，返回合并后的链表。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：lists = [[1,4,5],[1,3,4],[2,6]]
 *      输出：[1,1,2,3,4,4,5,6]
 *      解释：链表数组如下：
 *          [
 *            1->4->5,
 *            1->3->4,
 *            2->6
 *          ]
 *          将它们合并到一个有序链表中得到。
 *          1->1->2->3->4->4->5->6
 *
 * 示例 2：
 *      输入：lists = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：lists = [[]]
 *      输出：[]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *      <li>k == lists.length</li>
 *      <li>0 <= lists[i].length <= 500</li>
 *      <li>-10^4 <= lists[i][j] <= 10^4</li>
 *      <li>lists[i] 按 升序 排列</li>
 *      <li>lists[i].length 的总和不超过 10^4</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @since 2023/11/2 11:06
 */
public class LC0023MergeKSortedLists {
    static class Solution {
        /**
         * 分治合并
         */
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            return mergeKLists(lists, 0, lists.length - 1);
        }

        /**
         * 合并 lists 中指定范围的链表。
         * <p>过程：每次找到 left 和 right的中点 mid，对[left,mid]合并，再对[mid+1,right]，最后再对合并后的结果合并</p>
         *
         * @param lists 数组
         * @param left  左边界
         * @param right 右边界
         * @return 合并结果
         */
        private ListNode mergeKLists(ListNode[] lists, int left, int right) {
            if (left == right) {
                return lists[left];
            }
            if (left > right) {
                return null;
            }
            int mid = left + ((right - left) >> 1);
            return merge(mergeKLists(lists, left, mid), mergeKLists(lists, mid + 1, right));
        }

        private ListNode merge(ListNode list1, ListNode list2) {
            ListNode dummyHead = new ListNode();
            ListNode currNode = dummyHead;
            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    currNode.next = list1;
                    list1 = list1.next;
                } else {
                    currNode.next = list2;
                    list2 = list2.next;
                }
                currNode = currNode.next;
            }
            currNode.next = list1 != null ? list1 : list2;
            return dummyHead.next;
        }

        /**
         * 使用小根堆
         */
        public ListNode mergeKLists2(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            PriorityQueue<ListNode> heap = new PriorityQueue<>(lists.length, Comparator.comparingInt(n -> n.val));
            for (ListNode list : lists) {
                if (list != null) {
                    heap.add(list);
                }
            }
            ListNode dummyHead = new ListNode();
            ListNode currNode = dummyHead;
            while (!heap.isEmpty()) {
                ListNode minNode = heap.poll();
                currNode.next = minNode;
                currNode = currNode.next;
                if (minNode.next != null) {
                    heap.add(minNode.next);
                }
            }
            return dummyHead.next;
        }

        /**
         * 迭代
         */
        public ListNode mergeKLists3(ListNode[] lists) {
            if (lists == null || lists.length == 0) {
                return null;
            }
            ListNode res = null;
            for (ListNode list : lists) {
                res = merge(res, list);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        head1.next = new ListNode(4);
        head1.next.next = new ListNode(5);
        ListNode head2 = new ListNode(1);
        head2.next = new ListNode(3);
        head2.next.next = new ListNode(4);
        ListNode head3 = new ListNode(2);
        head3.next = new ListNode(6);
        ListNode[] lists = {head1, head2, head3};
        Solution solution = new Solution();
        Printer.printListNode(solution.mergeKLists(lists));
        Printer.printListNode(solution.mergeKLists(null));
        Printer.printListNode(solution.mergeKLists(new ListNode[0]));
    }
}